1. Field of the Invention
This invention relates to an improved computer graphics apparatus and method for comparing two or more digitally-stored images on a raster-scan display device.
2. Description of the Prior Art
The processing and analysis of digital images often requires comparison or combination of two different images that are related in some way, producing another digital image which represents the result. The specific application which led to the development of this invention is quality control and failure analysis of integrated circuit chips. Using the "voltage contrast" technique, digital images in which the intensity is correlated with voltage at each pixel can be collected. For example, an image from a scanning electron microscope of a faulty device can be compared with an image of a functioning one to locate the faults by visually comparing the differences between the two images. Similarly, in fields such as materials science, differences between successive images show propagation of failures in stressed parts. In other applications, the user is interested in regions where two images match rather than where they differ. For example, in biological and medical research the use of two-dimensional gel electrophoresis produces an image whose pattern represents the distribution of the components in a sample. To determine the content of an unknown sample, the unknown sample images may be matched against images of many standards, such as proteins, amino acids and nucleic acids.
A brief history of computer graphics as well as helpful definitions of many of the concepts and terms used by those skilled in the art are presented and discussed in Fundamentals of Interactive Computer Graphics by J.D. Foley and A. Van Dam, Addison-Wesley Publishing Co. (1982), at Chapter 1, Pages 18-22, Chapter 3, Pages 129-135 and Chapter 12, Pages 479, 488-500. Also see, Electronic Displays by Sol Sherr, John Wiley & Sons Publishing Co. (1979), and Computer Graphics Theory and Application by Tosiyasu and Kumii, Springer-Verlag Publishing Co. (1984).
The general concept of computer graphics displays of the kind having a refresh memory buffer connected to a raster-scan display is well explained in Sherr's book Electronic Displays. Sherr discusses refresh memory at pages 347-354, and the connection of the refresh memory to a raster-scan display under the heading "digital television" at pages 363-381.
The Foley and Van Dam, and the Tosiyasu and Kumii textbooks discuss the concept of generating apparent magnification on a display by causing one pixel in the image buffer to appear in more than one pixel on the display. They also explain the concept of transforming intensity values stored in the image buffer into new intensity values or colors by using a lookup table, and the concept of processing mathematical functions using a lookup table.
Foley and Van Dam explain at page 492 that only translation (roam) and integer scalings are available commercially. Integer scaling means zoom by integer numbers (1, 2, 3, etc.) so that a single pixel in the image buffer covers a 2 by 2, 3 by 3, etc. pixel area on the display. Tosiyasu and Kumii, two years later, stated that only binary (2, 4, 8...) or integer scalings are available commercially.
Foley and Van Dam discuss at pages 489-491 the concept of performing mathematical operations on two images using lookup tables. However, the images are assumed to be in the stacked bit planes (i.e. a one-to-one correspondence between pixels in all images). Our invention permits non-integer scaling relationships between the images. Also, nowhere in either test is the concept mentioned of concatenating the logic for processing mathematical functions to intensity or color lookup tables in order to process the mathematical function on the outputs of the lookup tables. The functions are assumed to be processed directly on the value stored in the image buffer. Our invention processes the mathematical function on the output of the color lookup tables, permitting either the function process (which may also be implemented as lookup tables), or the color lookup tables to be altered independently and both to be altered without affecting the data stored in the image buffer.
Foley and Van Dam also reference a paper published by the ACM (Association for Computing Machinery) SIGGRAPH (Special Interest Group for Graphics), 1980 Conference Proceedings, published as Computer Graphics 14(3) (July 1980) at pages 286-293. The paper is entitled Continuous Anti-aliased Rotation and Zoom of Raster Images by C. Weiman. This paper describes purely a software implementation of an algorithm for performing a continuous zoom. Although mention is made of the possibility of placing this algorithm into hardware, no disclosure is given of how this could be done. Further, the algorithm as shown requires modifying the data in the image memory buffer, which consumes time and destroys the relationship between the image pixel data and the color lookup tables. Preservation of image data when performing zoom operations is a purpose of our invention.
There are many commercially available image buffer display systems, some packaged as complete systems and some packaged as printed circuit boards for use with a host computer system. Some image buffer display systems contain "pipeline processors". These systems provide separate apparatus for altering the grey levels or colors assigned to the pixels in an image with lookup tables; for varying the apparent magnification ("zoom") or position ("pan" or "roam") of the displayed area within the digital image and for computing the results of operations on the pixels contained in the two digital images at high rates with said pipeline processor. The aforementioned functions are all treated independently in the prior art devices. These pipeline processors operate on pixel intensity without regard to assigned colors and either ignore screen zoom-roam altogether or assume a one-to-one correspondence between the two or more input pixels and between the input pixels and the output pixel. In addition a currently popular technique called "windowing" does not overcome these limitations, but merely divides the display into a number of regions, each of which is separately subject to the same limitations.
These pipeline processors cannot dynamically correct for differences between two or more images. They must correct the data in the stored image for registration, scaling, and grey-level normalization, separately before the high speed comparison can be done.
The following systems are typical of currently available apparatus. Imaging Technology Incorporated, in Woburn, Mass. 01801, markets a printed circuit board (or set of boards) for use with the IBM At series personal computers, under the mark PC-Vision.RTM., model number FG-100-AT. This product includes an image buffer, zoom and roam logic and color lookup tables (red, blue and green). However, only zoom magnifications of 2, 4 and 8 are available. All bit planes in the buffer are a synchronized stack; no independent zoom and roam is possible. No function processing exists between the color lookup tables and the DAC's. The host computer interface is described as a set of I/O-mapped registers allowing programs to control the functions of the board or set of boards.
Lexidata Corporation, in Billerica, Mass. 01865, markets a system under the name Imageview which incorporates the concept, described by Foley and Van Dam, of dividing stacked bit planes into two images, and using a lookup table to perform the mathematical operations. Here again, the images cannot be zoomed and roamed independently. The color and function lookup tables are the same, so that for two images of N-bits, a table with 2.sup.2N entries must be altered to change the mathematical function performed or the color assignments for either image. Our invention provides for independent zoom and roam and separates the color tables and function tables, permitting the color assignments for either image to be modified by altering only 2.sup.N entries in that image's individual color tables. This becomes significant very quickly as N becomes larger; if N is 8 (two 8-bit images), 2.sup.N is only 256, while 2.sup.2N is 65,536.
Recognition Concepts, Inc. in Incline Village, Nev. 89450 markets a system under the name Trapix 5500 which incorporates a pipeline processor. This means that mathematical operations are destructive to the data in the image memory. By contrast, our invention does not alter image memory but shows the result on the display. Zoom in the Trapix 5500 is limited to integer values from 1 to 8, and the pipeline processor cannot operate on the output of the color lookup tables.
We are aware of no other company which provides a system that can perform near continuous non-integer zoom in their display hardware. However, Dipix Systems Ltd., Ottawa, Ontario, Canada, K2E 7J5, markets a system under the name Aries II which claims to have a continuous zoom, although no means of accomplishing this is disclosed. Further investigation has revealed that the system is capable of zooming in the relatively coarse linear steps 1, 1.2, 1.4, 1.6, etc., while our invention can zoom in increments of less than 2 percent (1, 1.0159, 1.0323, 1.0492, etc.) near unity and in progressively larger steps at higher magnifications. The small steps are useful for image comparison since often the images are fairly close in scale and fine adjustments are needed. The larger steps are useful when interactively viewing a single image, since the magnification appears to accelerate when zooming in to examine a relatively small area in the image. This acceleration is visually appealing as opposed to steady linear magnification at very fine steps.
None of the systems discussed herein is capable of processing mathematical operations on two images which are zoomed (by non-integer factors) and roamed in different amounts relative to each other, and displaying the resulting images wihtout altering the data in the image memories. None of the systems have separate color lookup tables preceding function processing logic, permitting the color tables to be updated independently of the functions; and for processing the functions on the transformed values produced by the color lookup tables. None of these systems is capable of providing zoom magnifications in very small increments near unity and providing progressively larger magnifications steps at higher magnifications. Our invention provides all these capabilities.